﻿using System;

namespace AlgorithmWithCS.TreeAlgorithm
{
    /// <summary>
    /// 二叉树结点
    /// </summary>
    public class BinaryTreeNode<T>
    {
        public T data;
        public BinaryTreeNode<T>? left;
        public BinaryTreeNode<T>? right;
    }

    /// <summary>
    /// 二叉树，用二叉链表实现
    /// </summary>
    public class BinaryTree<T>
    {
        /// <summary>
        /// 根节点
        /// </summary>
        public BinaryTreeNode<T>? Root { get; set; }

        /// <summary>
        /// 初始化一棵空树
        /// </summary>
        public void Init()
        {
            Root = null;
        }

        /// <summary>
        /// 根据输入字符创建一颗二叉树
        /// 输入例子：12#245#23
        /// #标识空节点
        /// 采用前序遍历生成
        /// </summary>
        public void CreateByInput(BinaryTreeNode<int>? node)
        {
            var data = Console.Read();
            if (data == '#')
            {
                return;
            }

            node = new BinaryTreeNode<int>
            {
                data = data,
            };
            CreateByInput(node.left);
            CreateByInput(node.right);
        }

        /// <summary>
        /// 前序遍历
        /// </summary>
        /// <param name="node"></param>
        public void PreOrderTraverse(BinaryTreeNode<T>? node)
        {
            if (node == null)
            {
                return;
            }
            
            Console.Write($"{node.data}-");
            PreOrderTraverse(node.left);
            PreOrderTraverse(node.right);
        }

        /// <summary>
        /// 中序遍历
        /// </summary>
        /// <param name="node"></param>
        public void InOrderTraverse(BinaryTreeNode<T>? node)
        {
            if (node == null)
            {
                return;
            }
            
            InOrderTraverse(node.left);
            Console.Write($"{node.data}-");
            InOrderTraverse(node.right);
        }

        /// <summary>
        /// 后序遍历
        /// </summary>
        /// <param name="node"></param>
        public void PostOrderTraverse(BinaryTreeNode<T>? node)
        {
            if (node == null)
            {
                return;
            }
            
            PostOrderTraverse(node.left);
            PostOrderTraverse(node.right);
            Console.Write($"{node.data}");
        }
    }
}